//题目:
// 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
// 返回这三个数的和。
// 假定每组输入只存在恰好一个解。
#include<iostream>
#include<queue>
#include<unordered_map>
#include<limits.h>
#include<algorithm>

using namespace std;
//代码:
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        //1.暴力全排列 O(N^3)
        //2.排序 O(NlogN)
        sort(nums.begin(),nums.end());//-4 -1 1 2
        int diff=INT_MAX,ret=INT_MAX;
        for(int i=0;i<=nums.size()-3;i++)
        {
            int newtarget=target-nums[i];
            //在[i+1,nums.size()-1]找两个数，使其和与newtarget的差的绝对值最小
            int left=i+1,right=nums.size()-1;
            while(left<right)
            {
                int sum=nums[left]+nums[right];
                if(sum>newtarget)
                {
                    right--;
                    //方式left和right找过头了，下面的这个if判断条件就是判断abs的最佳条件
                    if(left<right && nums[left]+nums[right]<newtarget)
                    {
                        if(diff<abs(sum-newtarget))
                            diff=abs(sum-newtarget),ret=sum+nums[i];
                        if(diff<abs(nums[left]+nums[right]-newtarget))
                            diff=abs(sum-newtarget),ret=sum+nums[i];
                    }
                }
                else if(sum<newtarget)
                {
                    left++;
                    if(left<right && nums[left]+nums[right]>newtarget)
                    {
                        if(diff<abs(sum-newtarget))
                            diff=abs(sum-newtarget),ret=sum+nums[i];
                        if(diff<abs(nums[left]+nums[right]-newtarget))
                            diff=abs(sum-newtarget),ret=sum+nums[i];
                    }
                }
                else return target;
                if(diff>abs(sum-newtarget))
                        diff=abs(sum-newtarget),ret=sum+nums[i];
            }
        }
        return ret;
    }
};